package com.二叉树2;

import sun.awt.image.ImageWatched;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class 前序遍历二叉树 {
    static class Solution {
        public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            if(root == null){
                return list;
            }
            LinkedList<TreeNode> linkedList = new LinkedList<>();
            linkedList.add(root);
            while (linkedList.size() != 0){
                TreeNode treeNode = linkedList.pollFirst();
                list.add(treeNode.val);
                if(treeNode.left != null){
                    linkedList.add(treeNode.left);
                }
                if(treeNode.right != null){
                    linkedList.add(treeNode.right);
                }
            }
            return list;
        }

        /**
         * 高手的解答真的牛逼啊
         * @param root
         * @return
         */
        public List<Integer> preorderTraversal2(TreeNode root) {
          List<Integer> list = new ArrayList<>();
          if(root == null){
              return list;
            }
          Stack<TreeNode> stack = new Stack<>();
          stack.push(root);
          while (!stack .isEmpty()){
              TreeNode treeNode = stack.pop();
              list.add(treeNode.val);
              if(treeNode.right != null){
                  stack.push(treeNode.right);

              }
              if(treeNode.left != null){
                  stack.push(treeNode.left);
              }
          }
          return list;

        }
        public List<Integer> preorderTraversal3(TreeNode root) {
            List<Integer> list  = new ArrayList<>();
            if(root == null){
                return list;
            }
            Stack<TreeNode> stack  = new Stack<>();
            stack.push(root);
            while (!stack.empty()){
                TreeNode treeNode = stack.pop();
                list.add(treeNode.val);
                if(treeNode.right != null){
                    stack.push(treeNode.right);
                }
                if(treeNode.left != null){
                    stack.push(treeNode.left);
                }
            }
            return list;

        }
        public static void main(String[] args) {
                Solution solution = new Solution();
                List<Integer> list = solution.preorderTraversal3(new TreeNode( new int[]{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}));

        }
    }
}
